import com.sun.source.tree.Tree;
import tool.TreeNode;
import tool.TreeNodePrint;
import tool.input;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Description: 相同的数
 * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 * @Date:Create in 20:55  2022/7/25
 */
public class isSameTree0100 {
    public static void main(String[] args) {
        String s1 = "[1,2]";
        String s2 = "[1,null,2]";
        TreeNode p = input.getTree(s1);
        TreeNode q = input.getTree(s1);
//        TreeNodePrint.printTree(root);
        boolean bool = isSameTree(p, q);
        System.out.println(bool);
    }

    //递归法
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null) return true;
        if(p!=null&&q==null) return false;
        if(p==null&&q!=null) return false;
        if(p.val!=q.val) return false;
        boolean compareLeft= compare(p.left, q.left);
        boolean compareRight = compare(p.right, q.right);
        return compareLeft && compareRight;

    }

    private static boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right != null) {
            return false;
        }
        if (left != null && right == null) {
            return false;
        }
        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) {
            return false;
        }

        boolean compareOut = compare(left.left, right.left);
        boolean compareIn = compare(left.right, right.right);
        return compareOut && compareIn;
    }


    /**
     * 迭代法
     * 使用普通队列
     */
    public static boolean isSameTree2(TreeNode p, TreeNode q) {
        if(p==null&&q==null) return true;
        if(p!=null&&q==null) return false;
        if(p==null&&q!=null) return false;
        if(p.val!=q.val) return false;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(p);
        que.offer(q);
        while(!que.isEmpty()){
            TreeNode leftNode = que.poll();
            TreeNode rightNode = que.poll();
            if(leftNode==null&&rightNode==null) continue;
            if(leftNode==null || rightNode==null || leftNode.val!=rightNode.val){
                return false;
            }
            que.offer(leftNode.left);
            que.offer(rightNode.left);
            que.offer(leftNode.right);
            que.offer(rightNode.right);
        }
        return true;
    }
}
